// Package _24__二叉树中的最大路径和
// Date        : 2022/4/2 18:22
// Version     : 1.0.0
// Author      : 代码小学生王木木
// Email       : 18574945291@163.com
// Description :
package main

import "math"

// TreeNode
// @Description: 定义二叉树结构
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// max
// @Description:
// @param a
// @param b
// @return int
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

// maxPathSum
// @Description: 二叉树中的最大路径和
// @param root
// @return int
func maxPathSum(root *TreeNode) int {
	var ans = math.MinInt32
	var DFS func(node *TreeNode) int
	DFS = func(node *TreeNode) int {
		if node == nil {
			return 0
		}
		// 递归求左子树的最大值
		leftMaxSum := max(DFS(node.Left), 0)
		// 递归求右子树的最大值
		rightMaxSum := max(DFS(node.Right), 0)

		maxPath := node.Val + leftMaxSum + rightMaxSum
		ans = max(ans, maxPath)
		return node.Val + max(leftMaxSum, rightMaxSum)
	}
	DFS(root)
	return ans
}
